/*
https://leetcode.cn/problems/numbers-with-repeated-digits/submissions/578103693/
1012. 至少有1位重复的数字
数位DP
*/

class Solution {
private:

   int ans = 0;

public:

    void dfs(int mask, const string& s, int k, bool issame) {
        if(k == s.length()) {
            ++ans;
            return;
        }
        int t = issame ? s[k] - '0' : 9;
        for(int i = 0; i <= t; ++i) {
            if(mask & (1 << i)) {
                continue;
            }
            dfs(mask == 0 && i == 0 ? mask : mask | (1 << i), s, k + 1, issame && (i == t));
        }
    }

    int numDupDigitsAtMostN(int n) {
        string s = to_string(n);
        dfs(0, s, 0, true);
        cout << ans;
        return n - ans + 1;
    }
};